#include <iostream>
#include <exception>
using namespace std;

struct KA 
{
	int key;
	int assist;
	bool operator < (KA& other)
	{
		return key < other.key;
	}
	void print()
	{
		cout<<"("<<key<<","<<assist<<") ";
	}
};

void Swap(int* left, int* right)
{
	int tmp = *left;
	*left = *right;
	*right = tmp;
}

bool InsertSort(KA* arr, int length)
{
	for (int i=1; i<length; ++i)
	{
		int j = 0;
		for (; j<i; ++j)
		{
			//if(!CFunc(this, &arr[j], &arr[i]))
			if(arr[i] < arr[j])
				break;
		}

		for (int k=j+1; k<i; ++k)
		{
			if(arr[k] < arr[i])
			{
				exception e;
				throw e;
			}
		}

		if(j<i)
		{
			KA tmp = arr[i];
			//for(int y = i; y>j; --y)
			//{
			//	arr[y] = arr[y-1];
			//}
			memmove(&arr[j+1], &arr[j], (i-j)*sizeof(KA));
			arr[j] = tmp;
		}

		for(int x=0; x<length; ++x)
		{
			//cout<<arr[x]<<" ";
			arr[x].print();
		}
		cout<<endl;
	}
	return true;
}

void main()
{
	KA arr[10] = {{9,90}, {8, 1}, {2,20}, {8, 3} , {5,50}, {7,70}, {6,60}, {8, 2}, {4,40}, {3,30}};
	for(int i=0; i<10; ++i)
	{
		arr[i].print();
	}
	cout<<"\nStart Sorting....\n";
	InsertSort(arr, 10);
	cout<<"Sort Complete.\n";
	for(int i=0; i<10; ++i)
	{
		arr[i].print();
	}
	cin.get();
}